#define _CRT_SECURE_NO_WARNINGS
#include"pile.h"

void swap(piledata* a, piledata* b)
{
	piledata tmp = *a;
	*a = *b;
	*b = tmp;
}

void initial(pile* pi)
{
	pi->a = NULL;
	pi->capa = pi->sz = 0;
}

void printpile(pile* pi)
{
	assert(pi);
	assert(!emptypile(pi));
	int n = pi->sz;
	while (n--)
	{
		printf("%d ", pi->a[n]);
	}
	printf("\n");
}

void destorypile(pile* pi);

void adjustup(int* p,int chilen)
{
	int parent = (chilen-1)/2;
	while (chilen > 0)
	{
		if (p[chilen] < p[parent])
		{
			swap(&p[chilen], &p[parent]);
			chilen = parent;
			parent = (chilen - 1) / 2;
		}
		else
			break;
	}
}

void pushpile(pile* pi,piledata x)
{
	assert(pi);
	if (pi->capa == pi->sz)
	{
		int newcapa =pi-> capa == 0 ? 4 :pi-> capa * 2;
		piledata* tmp = (int*)realloc(pi->a, sizeof(piledata) * newcapa);
		if (tmp == NULL)
		{
			perror("realloc error");
			exit(-1);
		}
		pi->a = tmp;
		pi->capa = newcapa;
	}
	pi->a[pi->sz] = x;
	pi->sz++;
	adjustup(pi->a, pi->sz - 1);
}

void adjustdown(int* p,int n, int parent)
{
	int minchilen = parent * 2+1;
	while (minchilen < n)
	{
		if (minchilen + 1 < n && p[minchilen] < p[minchilen + 1])
		{
			minchilen++;
		}
		if (p[parent] < p[minchilen])
		{
			swap(&p[parent], &p[minchilen]);
			parent = minchilen;
			minchilen = parent * 2 + 1;
		}
		else
			break;
	}
}

void poppile(pile* pi)
{
	assert(pi);
	assert(!emptypile(pi));
	swap(&pi->a[0], &pi->a[pi->sz-1]);
	pi->sz--;
	adjustdown(pi->a,pi->sz, 0);
}

piledata gettop(pile* pi)
{
	assert(pi);
	assert(!emptypile(pi));
	return pi->a[0];
}

bool emptypile(pile* pi)
{
	assert(pi);
	return pi->sz == 0;
}

int sizepile(pile* pi)

{
	assert(pi);
	return pi->sz;
}
